Databases are computerized information storage and retrieval systems. A relational database management system (RDBMS) is a database management system (DBMS) that uses relational techniques for storing and retrieving data. Relational databases are organized into tables that comprise rows, all rows having the same columns of data. Each column maintains information on a particular type of data for the data records that comprise the rows. The rows are formally called tuples or records. A database typically comprises many tables and each table typically comprises tuples and columns. The tables are typically stored on direct access storage devices (DASD), such as magnetic or optical disk drives for semi-permanent storage.
Tables are searched using, for example, a Structured Query Language (SQL), which specifies search operations or predicates to perform on columns of tables in the database. The search operations qualify rows in the database tables that satisfy the search conditions. Relational database management system (RDBMS) software using a Structured Query Language (SQL) interface is well known in the art. The SQL interface has evolved into a standard language for RDBMS software and has been adopted as such by both the American National Standards Institute (ANSI) and the International Standards Organization (ISO).
Indexes are used with database implementations to provide good application query performance. Indexes are typically constructed using the data values in one or more columns of an RDBMS table row (e.g., using information such as product number, customer name, address, etc.). This information is represented by bit strings that define numeric or character values. An RDBMS may implement a B-tree index that generates a binary tree based on the bit string values. When a query includes values of columns contained in an index, the B-tree index can be scanned quickly to find the candidate rows with these column values.
Indexing techniques are used to quickly access data. Spatial data is typically information associated with geometric shapes such as lines, points, poly-lines, polygons, and surfaces. Consequently, spatial data is typically represented by one or more coordinates comprising pairs of numeric values (x, y) corresponding to, for example, locations on the earth. Spatial data is often very large and may have two, three, or more dimensions. Queries against spatial data typically are more complex than identifying a specific row or a set of rows with values between a simple range.
The indexing techniques for traditional alphanumeric data are typically based on a linear ordering of key values in a single dimension. B-tree indexing is one of the most common techniques used but this is only suited for single dimension data, not multi-dimensional data such as spatial data. Various indexing techniques have been developed specifically for multi-dimensional data. Grid indexing is one of these indexing techniques associated with searching spatial multidimensional data.
Although this technology has proven to be useful, it would be desirable to present additional improvements. The grid cell size used in grid indexing strongly affects the efficiency of accessing spatial data by techniques that employ grid indexing. A problem has been to refine the determination of particular grid cell sizes and thereby reduce the overhead associated with searching a spatial data set via grid indexing using conventional techniques. More particularly, a problem has been to reduce the computational processing to perform the sampling that occurs during statistics collection. Such data is used to determine the proper grid cell size.
Those skilled in the art will appreciate the technique of accessing spatial data by determining overlap of a geometric shape with a grid cell matrix. A grid index contains one index entry for each grid cell that overlap a geometric shape. The storage and processing increases with the number of grid cells that overlap a geometric shape. This aspect would suggest large grid cell sizes compared to geometric shape sizes in order to approach a one-to-one relationship of index entries to geometric shapes. Typical spatial queries are based on finding geometric shapes which overlap a rectangular query region. The grid index technique will scan all index entries in the grid cells which overlap the query region. As the grid size increases, more index entries outside the query region will need to be examined and discarded. An optimal grid size must determine the appropriate trade-off between these two opposing considerations.
A geometric shape that is typically the subject of spatial data may be approximated by a rectangle. When a rectangle bounds the geometric shape with a minimum enclosure, it is referred to as a “minimum-bounding rectangle.” A minimum-bounding rectangle is defined to approximate a geometric shape located in a space. Coordinates located on a grid reference the minimum-bounding rectangle and the approximated geometric shape that represent the location of the minimum-bounding rectangle. For example, the coordinates on a grid that correspond to the corners of the minimum-bounding rectangle are stored and used to reference the minimum-bounding rectangle.
An index enables fast access of a certain subset of data contained in a larger set of data. The index comprises a data structure and the techniques used to build, maintain, and search the data structure for the purpose of accessing a subset of data. For example, an index may define a data structure that is used to access a specific geometric shape included in a set of spatial data. The particular index of the present example may define a data structure that contains references to the minimum-bounding rectangles associated with various geometric shapes in a spatial data set. By accessing locator references associated with the minimum-bounding rectangles, the process of accessing particular geometric shapes in a spatial data set is simplified.
Conventional techniques have typically required significant resources to locate a geometric shape in a spatial database. The lack of an efficient process for determining an index that facilitates streamlined location of minimum-bounding rectangles and associated geometric shapes has contributed to inefficient access of information in spatial databases with grid indexing. One problem has been to minimize the amount of data that is processed in order to determine an efficient grid cell size. That is, there exists a need to reduce from the processing required to perform sampling during statistics collection.
What is therefore needed is a system, a computer program product, and an associated method to improve the determination of the grid cell size when grid-indexing techniques are applied to spatial data on a computer system for significantly reducing the processing time. The need for such a solution has heretofore remained unsatisfied.